
//739.每日温度
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& nums) {
        //从右向左,维护下一个可能满足的位置
        int n=nums.size();
        stack<pair<int,int>>  st; //既要存放下标又要有温度
        st.push({nums[n-1],n-1});
        
        vector<int> ret(n);
        for(int i=n-2;i>=0;i--)
        {
            while(!st.empty()&&st.top().first<=nums[i]) st.pop();  //如果栈顶元素小,出栈
        
            if(st.empty()) ret[i]=0;   //栈为空,没有满足的温度
            else ret[i]=st.top().second-i;   //栈不为空

            st.push({nums[i],i});  //将当前位置加入到栈中
        }
        return ret;
    }
};